• Home
• Staff & Students
• Vacancies

Guillaume Obozinski

 

 

Wednesday 10th September 2014

Time: 4pm

 

Basement Seminar Room

Alexandra House, 17 Queen Square, London, WC1N 3AR

 

Tight convex relaxations for sparse matrix factorization

In this talk, I'll present recent work in collaboration with Emile Richard and Jean-Philippe Vert. We considered statistical learning problems in which the parameter is a matrix which is the sum of a small number of sparse rank one (non-orthogonal) factors, and which can be viewed as generalizations of the sparse PCA problem with multiple factors. Based on an assumption that the sparsity of the factors is fixed and known, we designed a matrix norm which provides an tight although NP-hard convex relaxation of the learning problem. We considered also a natural variant of that norm related to the planted clique problem. I will discuss the sample complexity of learning the matrix in the rank one case and show that considering a computationally more expensive convex relaxation leads to an improvement of the sample complexity by an order of magnitude as compared with the usual convex regularization considered, like combinations of the $\ell_1$-norm and the trace norm. I will then describe an algorithm, relying on a rank-one sparse PCA oracle to solve the convex problems considered and illustrate that, in practice, when state-of-the-art heuristic algorithms for rank one sparse PCA are used as surrogates for the oracle, our algorithm outperforms other existing methods.